1. Technical Field of the Invention
The present invention refers to an improved optimal mapping of LUT based FPGA. In particular the invention relates to a system that optimizes the design area in FPGA by exploring reconvergent paths in conjunction with Fan out replication in LUT mapping.
2. Description of Related Art
A programmable logic array device has a plurality of logic elements and an interconnect structure for conveying signals between logic elements. In LUT (Look Up Table) based FPGA's (Field Programmable Gate Arrays), mapping is done prior to the placement and routing of the design in FPGA. The objective of LUT mapping is to reduce the area/depth of the mapped solution.
In LUT based FPGA's, optimal mapping of gates into LUT's is done while ensuring that the number of transitive fan-ins to sink is always less than or equal to the number of LUT inputs. FIG. 1 illustrates the mapping process as a part of the FPGA development flow. 1.1 in the figure indicates the Gate Level Netlist as an input to the Optimizer Block that outputs Optimized Gate Level Netlist 1.2. The optimized netlist is then Mapped into LUT as shown in the 1.3 that is followed by Packing LUT's in to Programmable Logic Blocks (PLB's) 1.4. Then the design is simulated for Placement and Routing 1.5, 1.6. The bit stream is generated as in the Configuration Bits of the Design block 1.7. The bit stream is then downloaded in the FPGA to configure the FPGA as shown in the block 1.8. FIG. 2 illustrates a prior art Mapping process in LUT based FPGA's. 2.1 is Directed Acyclic Graph (DAG) that represents the mapping data as nodes, wherein the nodes in the DAG simulate the LUT's in the FPGA. 2.1 also illustrates initialization of the inputs to the LUT's (k) and the initialization of the fan-out factor. Block 2.2 illustrates performing a topological sort on the DAG. Block 2.3 illustrates the Computation of the Dependency variable for each node in the graph, whereby the dependency is computed keeping in view that the nodes are analyzed for their respective inputs and outputs. Block 2.4 performs check on the Dependency Variable till it is greater than the variable k. Block 2.5 shows the computation of the Priority Variable (Fc) for all the children of the node under consideration, and performing the same function for all other nodes in the Directed Acyclic Graph. Priority Variable (Fc) is a function of the following:                Contribution Variable (Zc), where c in the suffix denotes the children of the node.        Number of fan-outs (Oc) for the children of the node under consideration.        Fan-out Factor (FF) variable.        
Block 2.6 sorts the list of the children of the node under consideration in the descending order of their priority values followed by block 2.7 that assigns LUT's to the children of the node under consideration until the dependency variable is less than k plus one.
Block 2.8 assigns a LUT to each output of a given node that have been left unassigned.
The computations for the Contribution Variable, Dependency variable, and the Priority Function is as shown below:                Let a given design be represented by a directed acyclic graph (DAG) G(V, E) where each vertex v in V represents a Boolean function and each directed edge (v, u) represents a connection between the output of v and the input of u.        Let VI denotes the set of nodes for which LUT is assigned.        That is, VI={vεV: a LUT is assigned to v}.        Contribution Zv:        For each PI v, Zv=1,        For each vεVI, Zv=1,        For all the other vertices vεV, Zv=Zu1+Zu2+ . . . +Z1         where u1, u2, . . . , u1 are all the children of v.        Dependency dv:        a) For each PI v, dv=1        b) For all other vertices vεV, dv=Zu1+Zu2+ . . +Z1 where u1, u2, . . . , u1 are all the children of v.        Priority Function Fv:Fv=F(Zv, Ov, FF)=Zv+FF*Ov        Where Ov is the number fan outs of v and FF is a suitable fan out factor.        
The prior art Level Map method does not take into account of reconvergent paths and fan-out replication effectively, therefore it is essential to provide a system for optimizing design area in FPGA by exploring reconvergent paths in conjunction with fan-out replication in LUT mapping.